package DataStructure.tree.binaryTree.binaryTreeApply;

import DataStructure.tree.binaryTree.binaryTreeRealize.BinaryTreeImpl;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/1/8
 * @author—Email liujunfirst@outlook.com
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 树的左视图
 * 假设一颗树：
 * 1
 * 2       3
 * 4      5
 * 打印的左视图为：1，2，4
 */
public class TreeLeftView {

    List<Integer> list = new ArrayList();

    public int[] print(BinaryTreeImpl root) {
        if (root == null) {
            return new int[]{};
        }
        list.clear();
        Queue<BinaryTreeImpl> q = new LinkedList();
        q.add(root);
        list.add(root.value);
        BinaryTreeImpl front = root;
        BinaryTreeImpl tail = root;
        while (!q.isEmpty()) {
            BinaryTreeImpl node = q.poll();
            if (node.left != null) {
                q.add(node.left);
                tail = node.left;
            }
            if (node.right != null) {
                q.add(node.right);
                tail = node.right;
            }
            if (front == node) {
                if (!q.isEmpty()) {
                    list.add(q.peek().value);
                    front = tail;
                }
            }
        }
        int[] a = list.stream().mapToInt(Integer::intValue).toArray();
        return a;
    }
}
